import java.util.*;

public class BinaryTree {
    class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int i;
    public TreeNode createTree(String str){
        TreeNode root = null;

        if (str.charAt(i) != '#') {
            /*
            * 节点才创建 所以不需要判断所有节点是否为空不是判断左右节点是否有值
            * */
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }

    public TreeNode createTree() {
        TreeNode a = new TreeNode('A');
        TreeNode b = new TreeNode('B');
        TreeNode b1 = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');
//
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        e.right = h;
        c.right = g;
        c.left = f;

//        a.left = b;
//        a.right = b;
//        b1.left = c;
//        b1.right = d;
//        b.left = d;
//        b.right = c;


        return a;
    }

    // 前序非递归遍历
    public void preorderTraversalNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                System.out.print(cur.val + " ");
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            cur = tmp;
            cur = cur.right;
        }
        System.out.println();
    }

    // 中序非递归遍历
    public void inorderTraversalNor(TreeNode root) {
        if(root == null){
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode tmp = stack.pop();
            System.out.print(tmp.val + " ");
            cur = tmp;
            cur = cur.right;
        }
        System.out.println();
    }


    public int perpron;
    //从前序与中序遍历序列构造二叉树
    //preorder 前序 inorder 中序
    public TreeNode UsePreAndInorderCreateTree(int[] preorder, int[] inorder) {

        return UsePreAndInorderCreateTreeChild(preorder,inorder,0,0,inorder.length-1);
    }
    public TreeNode UsePreAndInorderCreateTreeChild(int[] preorder, int[] inorder,int begin,int ir,int end) {
        if(begin > end){
            return null;
        }
        TreeNode root = new TreeNode(preorder[perpron]);

        int rootIndex = findValue(inorder,preorder[perpron]);
        perpron++;

        root.left = UsePreAndInorderCreateTreeChild(preorder,inorder,begin,rootIndex,rootIndex-1);
        root.right = UsePreAndInorderCreateTreeChild(preorder,inorder,rootIndex+1,rootIndex,end);

        return root;
    }

    private int findValue(int[] num,int val){
        for(int i = 0 ; i < num.length ; i++ ){
            if(num[i] == val){
                return i;
            }
        }
        return -1;
    }

    public int inverseSize;
    public TreeNode UseInAndPostCreateTree(int[] inorder, int[] postorder) {
        inverseSize = inorder.length - 1;

        return UseInAndPostCreateTreeChild(inorder,postorder,0,inorder.length - 1);
    }

    public TreeNode UseInAndPostCreateTreeChild(int[] inorder, int[] postorder,int begin,int end) {
        if(begin > end){
            return null;
        }
        TreeNode root = new TreeNode(postorder[inverseSize]);
        int rootIndex = findValue(inorder,postorder[inverseSize]);
        inverseSize--;

        root.right = UseInAndPostCreateTreeChild(inorder,postorder,rootIndex + 1,end);
        root.left = UseInAndPostCreateTreeChild(inorder,postorder,begin,rootIndex - 1);

        return root;
    }


    //二叉树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null){
            return null;
        }
        if(q == root || p == root)
            return root;
        if(root.left == p && root.right == q)
            return root;

        TreeNode LeftTree = lowestCommonAncestor(root.left,p,q);
        TreeNode RigthTree = lowestCommonAncestor(root.right,p,q);

        if(LeftTree != null && RigthTree != null)
            return root;
        if(LeftTree == null)
            return RigthTree;

        return LeftTree;
    }

    public void levelOrder1(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur.val);
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
    }



}
